class Solution {

    private static final int[] dx = new int[]{0, 1, 0, -1};
    private static final int[] dy = new int[]{1, 0, -1, 0};
    private final Node root = new Node();
    private boolean[][] visited;
    private List<String> ans;
    private static final int LENGTH = 26;
    int m;
    int n;
    private static class Node {
        String word;
        Node[] child;
        Node() {
            this.word = null;
            this.child = new Node[LENGTH];
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        ans = new ArrayList<>();
        visited = new boolean[m][n];
        for (String word : words) {
            insertTrie(word);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root);
            }
        }
        return ans;
    }

    private void dfs(char[][] board, int x, int y, Node node) {
        int idx = board[x][y] - 'a';
        Node father = node;
        if (node.child[idx] == null) {
            return;
        } else {
            node = node.child[idx];
        }
        if (node.word != null) {
            ans.add(node.word);
            node.word = null;
        }
        if (Arrays.stream(node.child).filter(Objects::isNull).count() == LENGTH) {
            father.child[idx] = null;
        }
        visited[x][y] = true;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                continue;
            }
            if (!visited[nx][ny]) {
                dfs(board, nx, ny, node);
            }
        }
        visited[x][y] = false;
    }

    private void insertTrie(String word) {
        Node curr = root;
        for (char ch : word.toCharArray()) {
            int nextIdx = ch - 'a';
            if (curr.child[nextIdx] == null) {
                curr.child[nextIdx] = new Node();
            }
            curr = curr.child[nextIdx];
        }
        curr.word = word;
    }

}
